package leetcode

import kotlinetc.println

//https://leetcode.com/problems/search-insert-position/
//todo
/**
Given a sorted sort.getArray and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the sort.getArray.

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0
 */
fun main(args: Array<String>) {

    searchInsert(intArrayOf(1,3,5,6),1).println()
}
//Classic
fun searchInsert(nums: IntArray, target: Int): Int {

    var left = 0
    var right = nums.size - 1

    if (target>nums.last())return  right+1

    while (left < right) {
        val mid = (left + right) / 2

        when {
            nums[mid] == target -> return mid
            nums[mid] < target -> left = mid + 1
            else -> right = mid
        }
    }
    return right
}